/*
Find Minimum in Rotated Sorted Array Total Accepted: 48892 Total Submissions: 146847 My Submissions Question Solution
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}


class Solution {
public:
	int findMin(vector<int>& nums) {


		vector<int>::iterator it;
		it = unique(nums.begin(),nums.end());
		nums.resize(distance(nums.begin(),it));

		int begin = 0;
		int end = nums.size() - 1;
		while (begin<=end)
		{
			int mid = begin + (end - begin) / 2;
			if (nums[mid]>nums[nums.size()-1])
			{
				begin = mid + 1;
			}
			else
			{
				end = mid - 1;
			}


		}

		return nums[begin];
	}

};

int main(int argc, char* argv[])
{


	int a[] = { 4, 5, 6, 7, 0, 1, 2 };
	vector<int> vec(a, a + sizeof(a) / sizeof(int));


	int result;
	Solution s;
	result = s.findMin(vec);
	//cout << "The result is : " << result << endl;
	//result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;